#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
/*
 * @lc app=leetcode.cn id=114 lang=cpp
 *
 * [114] 二叉树展开为链表
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 递归的方法
    void flatten(TreeNode* root) {
        TreeNode node; TreeNode* cur = &node;
        helper(root, cur);
    }

    void helper(TreeNode* root, TreeNode* &cur) {
        if (!root || !cur) return;
        TreeNode* right = root->right; // 保存right节点
        root->right = nullptr; // right置空
        cur->right = root; // 
        cur = cur->right;
        helper(root->left, cur); 
        root->left = nullptr;
        helper(right, cur);
    }

    // 迭代的方法
    void flatten(TreeNode* root) {
        TreeNode node; TreeNode *cur = &node;
        while (root) {
            TreeNode* left = root->left;
            if (!left) { root = root->right; continue;}
            TreeNode* pre = left;
            while (pre->right) pre = pre->right;
            pre->right = root->right;
            root->right = left;
            root->left = nullptr;
            root = root->right; 
        }
    }

};
// @lc code=end

